package com.cd.algorithm.order.code;

import java.util.Arrays;

public class HeapSort {

    public static void main(String[] args) {
        int[] a={5,2,4,6,1,3,7,9,8,10,11,13,12,15,14};
        System.out.println("Before sorting:"+ Arrays.toString(a));
        heapSort(a);
        System.out.println("After sorting:"+ Arrays.toString(a));
    }

   public static void heapSort(int[] a){
        int n=a.length;
        //build max heap
        for(int i=n/2-1;i>=0;i--){
            heapify(a,n,i);
        }
        //extract max element and put it at the end of the array
        for(int i=n-1;i>=0;i--){
            int temp=a[0];
            a[0]=a[i];
            a[i]=temp;
            heapify(a,i,0);
        }
    }

    public static void heapify1(int[] a,int n,int i){
        int largest=i;
        int l=2*i+1;
        int r=2*i+2;
        if(l<n && a[l]>a[largest]){
            largest=l;
        }
        if(r<n && a[r]>a[largest]){
            largest=r;
        }
        if(largest!=i){
            int temp=a[i];
            a[i]=a[largest];
            a[largest]=temp;
        }
    }


    public static void heapify(int[] a,int n,int i){
        int largest=i;
        int l=2*i+1;
        int r=2*i+2;
        if(l<n && a[l]>a[largest]){
            largest=l;
        }
        if(r<n && a[r]>a[largest]){
            largest=r;
        }
        if(largest!=i){
            int temp=a[i];
            a[i]=a[largest];
            a[largest]=temp;
            heapify(a,n,largest);
        }
   }

static class myTest{

    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 6, 1, 3,15,34,67,89,12,7,9,8,10,11};
        System.out.println("Before sorting: " + Arrays.toString(arr));
        sort(arr);
        System.out.println("After sorting: " + Arrays.toString(arr));
    }


    // 主要的堆排序方法
    public static void sort(int[] arr) {
        // 构建最大堆
        buildMaxHeap(arr);
        //上浮操作
        for (int i = arr.length - 1; i > 0; i--) {
            //交换堆顶元素和最后一个元素
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            //最大堆调整
            heapify(arr, i, 0);
        }
    }

    // 构建最大堆
    public static void buildMaxHeap(int[] arr) {
        int length = arr.length;
        //从最后一个非叶子节点开始，到根节点
        for (int i = length / 2 - 1; i >= 0; i--) {
            // 最大堆的构建
            heapify(arr, length, i);
        }
    }

    //堆化
    public static void heapify(int[] arr, int length, int i) {
        int left = 2* i +1;
        int right = 2*i +2;
        int largest = i;
        if(left<length && arr[left] > arr[largest]){
            largest = left;
        }

        if(right<length && arr[right] > arr[largest]){
            largest = right;
        }

        if(largest!= i){
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, length, largest);
        }
    }
}

}
